package pacman;

import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class InfoTree {
	
	GameModel gameModel;			// game model to get stuff
	private InfoNode rootElement;	// the root node of the tre
	int totalit = -1;				// number of iteration/level of the tree
	int m_gameSizeX = 28;			// x size of the game
    int m_gameSizeY = 31;			// y seize of the game
  	int[][] m_gameState;			// grid for tree to represent the game
  	List<Direction> desiredPath;	// = new LinkedList<Direction>(); 
  	List<Direction> fullPath;		// full path with no elims yet
	
	public InfoTree(GameModel gameModel, Point p) {
		this.gameModel = gameModel;
		Info i = new Info(p, gameModel, 1);
		InfoNode n = new InfoNode(i);
		rootElement = n;
	}

	public InfoNode getRootElement() {
		return this.rootElement;
	}
	
	public void setRootElement(InfoNode rootElement) {
		this.rootElement = rootElement;
	}

	public List<InfoNode> toList() {
		List<InfoNode> list = new ArrayList<InfoNode>();
		walk(rootElement, list);
		return list;
	}    

	public String toString() {
		return toList().toString();
	}
	
	private void walk(InfoNode element, List<InfoNode> list) {
		list.add(element);
		for (InfoNode data : element.getChildren()) {
			walk(data, list);
		}
	}
	
	/**
	 * Build the tree using the rootElement for a give number of iteration
	 * @param p				the location to look at (for recursion, null for start)
	 * @param interation	the level in the tree its currently at (deducted for recursion)
	 * @return Node			next Node to look at for recursion
	 */
	Point prev = null;
	public InfoNode build(int iteration, Point p) {
		InfoNode node = null;
		Point pt = null;
		Point temp = null;
		int[] dir = new int [4];

		// if point p is null meaning we are beginning of tree thus use rootElement
		if(p==null){
			// set up stuff for new build of tree
			m_gameState = new int[m_gameSizeX][m_gameSizeY];
			if(totalit < iteration) totalit = iteration;
			reset_gState();
			node = rootElement;
			p = node.data.getPoint();
			m_gameState[p.x][p.y] = totalit - iteration;
			prev = p;
		}else{
			if (p.x == -1) {
				p.x = m_gameSizeX-1;
				System.out.println("OUT!!!");
			}
			if (p.x == m_gameSizeX) {
				p.x = 0;
				System.out.println("OUT!!!");
			}
			if (p.y == -1) {
				p.y = m_gameSizeY-1;
				System.out.println("OUT!!!");
			}
			if (p.y == m_gameSizeY) {
				p.y = 0;
				System.out.println("OUT!!!");
			}
			
			Info i = new Info(p, gameModel, totalit - iteration);
			node = new InfoNode(i);
		}

		iteration--;
		node.getDirection(gameModel, dir);
		
		if(iteration >= 0){
			temp = prev;
			for(int i=0; i<4; i++){
				if(dir[i] == 1){
					if(i==0) pt = new Point(p.x,p.y-1);
					if(i==1) pt = new Point(p.x,p.y+1);
					if(i==2) pt = new Point(p.x-1,p.y);
					if(i==3) pt = new Point(p.x+1,p.y);
					
					//printspace(iteration);
					//System.out.println("Iter:"+iteration+" At ["+p.x+" "+p.y+"]"+" Point ["+pt.x+" "+pt.y+"]"+" Prev ["+prev.x+" "+prev.y+"] Dir: "+dir[i]);

					// CONDITION COULD BE PUT HERE FOR PRUNING WHEN BUILDING!!!
					if(!pt.equals(prev)){
						if(!been(pt, totalit - iteration)){
							m_gameState[pt.x][pt.y] = totalit - iteration;
						}
						prev = p;
						InfoNode child = build(iteration, pt);
						node.addChild(child);
						prev = temp;
					}
				}
			}
		}else{
			return node;
		}
		return node;
	}

	/**
	 * Helper method to reset the game grid each time we build tree.
	 */
	private void reset_gState() {
		if (m_gameState == null){
			m_gameState = new int[m_gameSizeX][m_gameSizeY];
		}
		for(int i=0; i<m_gameSizeY; i++){
			for(int j=0; j<m_gameSizeX; j++){
				m_gameState[j][i] = -1;
			}
		}
	}

	/**
	 * Helper method in building the Tree.
	 * Determine if the tree been to a given location.
	 * @param p				the location to look at
	 * @param interation	the level in the tree
	 * @return True			if is has been at higher level (dont look at pt)
	 * @return False		if it has not been or been at a lower level (look at pt)
	 */
	private boolean been(Point p, int interation) {
		if(p.x<0 || p.y<0 || p.x>=m_gameSizeX || p.y>=m_gameSizeY){
			return true;
		}else if(m_gameState[p.x][p.y] == -1){
			return false;
		}else if(m_gameState[p.x][p.y] > interation){
			return false;
		}
		return true;
	}

	// TO BE REMOVED
	private void printspace(int iteration) {
		for(int i=0; i<(totalit-iteration); i++){
			System.out.print("  ");
		}
	}

	/**
	 * This will bring the game out in a grid showing the tree
	 */
	public void printTree() {
		System.out.println();
		for(int i=0; i<m_gameSizeY; i++){
			for(int j=0; j<m_gameSizeX; j++){
				if(m_gameState[j][i]!=-1){
					if(m_gameState[j][i]>9){
						System.out.print(m_gameState[j][i]+" ");
					}else{
						System.out.print(m_gameState[j][i]+"  ");
					}
				}else{
					System.out.print("   ");
				}
			}
			System.out.println();
		}
	}

	
	/** BELOW HERE CAN HAVE VARIOUS SEARCH METHOD FOR TREE **/
	
	void calculateTree() {
		calculateTreeValues(rootElement);
		//System.out.println("\n"+rootElement.totalValue);
	}
	
	/**
	 * recursion: calculate the value for given node
	 */
	void calculateTreeValues(InfoNode node) {		
		List<InfoNode> children = node.getChildren();		
		if(children == null){
			node.calculateValue();
			return;
		}
		for (InfoNode child : children) {
			calculateTreeValues(child);
		}
		node.calculateValue();		
	}
	
	List<Direction> getDesiredPath() {
		desiredPath = new LinkedList<Direction>();
		fullPath = new LinkedList<Direction>();
		buildDesiredPath(rootElement);
		if(rootElement.getData().getValue() < 0){
			oppositeDir();
		}
		return desiredPath;
	}
	
	void oppositeDir(){
		desiredPath = new LinkedList<Direction>();
		Direction d = null;
		if (gameModel.m_things[0].m_direction == 1){
			desiredPath.add(d.setValue(2));
		}else if (gameModel.m_things[0].m_direction == 2){
			desiredPath.add(d.setValue(1));
		}else if (gameModel.m_things[0].m_direction == 3){
			desiredPath.add(d.setValue(4));
		}else if (gameModel.m_things[0].m_direction == 4){
			desiredPath.add(d.setValue(3));
		}
	}
	
	/**
	 * recursion: returns the list of the chosen path
	 * Note:
	 * - first if statement check for the first direction and make sure it is not already the direction the pacman is going
	 * - second if statement check if the direction is already in the list since pacman only need to be told only once
	 * TODO: logic doesnt work if pacman were to really go pass a particular turn. 
	 * eg. pacman going right (couple of time) and then go up on the second up. 
	 * - pacman is already going right so next queue is up, aka next up not second up.
	 * - possible fix is manually queue each node and see if dir possible equals next direction (doesnt work, need better logic)
	 */
	int test = 0;
	void buildDesiredPath(InfoNode node) {
		if (node.getChildren().isEmpty()) {
			return;
		}
		
		if(desiredPath.isEmpty()){
			//System.out.println("Start build. Pacman going - "+gameModel.m_things[0].m_direction+" "+(node.getToDirection().dir==gameModel.m_things[0].m_direction));
			if(!(node.getToDirection().dir==gameModel.m_things[0].m_direction)){
				desiredPath.add(node.getToDirection());
				fullPath.add(node.getToDirection());
				//System.out.println("Step "+test+": point ["+node.getData().getPoint().x+" "+node.getData().getPoint().y+"] dir = "+node.getToDirection());
				test++;
			}else{
				fullPath.add(node.getToDirection());
				//System.out.println("Alread going dir "+node.getToDirection());
			}
//		}else if(!(node.getToDirection()==desiredPath.get(desiredPath.size()-1))){
//			desiredPath.add(node.getToDirection());
//			fullPath.add(node.getToDirection());
//			//System.out.println("Step "+test+": point ["+node.getData().getPoint().x+" "+node.getData().getPoint().y+"] dir = "+node.getToDirection());
//			test++;
		}else{
			fullPath.add(node.getToDirection());
			//System.out.println("repeat");
		}
		
		//Node<T> nextNode = new Node<T>();
		//List<Node<T>> children = node.getChildren();
		buildDesiredPath(node.getToNode());
	}
	
	int getTreeValue() {
		return rootElement.getNodeValue();
	}

	// TEMPORAY PRINTING
  	double[][] m_gameValue;
	void printTreeNodeValues() {
		if (m_gameValue == null){
			m_gameValue = new double[m_gameSizeX][m_gameSizeY];
		}
		for(int i=0; i<m_gameSizeY; i++){
			for(int j=0; j<m_gameSizeX; j++){
				m_gameValue[j][i] = 999;
			}
		}
		printTreeNodeValues(rootElement);
		printValue();
	}
	int temp = 0;
	void printTreeNodeValues(InfoNode node) {
		List<InfoNode> children = node.getChildren();
		String output = "";
		for(int i=0; i<temp; i++){
			output += "  ";
		}
		//System.out.println(output+"node: ["+node.data.getPoint().x+" "+node.data.getPoint().y+"] value: "+node.data.getValue()+" children: "+children.size()+" total value: "+node.getNodeValue());
		m_gameValue[node.data.getPoint().x][node.data.getPoint().y] = node.getNodeValue()/100;
		temp++;
		for (InfoNode child : children) {
			printTreeNodeValues(child);
		}
		temp--;
	}
	public void printValue() {
		System.out.println();
		for(int i=0; i<m_gameSizeY; i++){
			for(int j=0; j<m_gameSizeX; j++){
				if(m_gameValue[j][i]!=999){
					if(m_gameValue[j][i]>99||m_gameValue[j][i]<-9){
						System.out.print((int)m_gameValue[j][i]+"");
					}else if((m_gameValue[j][i]<0 && m_gameValue[j][i]>=-9) || (m_gameValue[j][i]>9 && m_gameValue[j][i]<=99)){
						System.out.print((int)m_gameValue[j][i]+" ");
					}else if(m_gameValue[j][i]>=0 && m_gameValue[j][i]<9){
						System.out.print((int)m_gameValue[j][i]+"  ");
					}
				}else{
					System.out.print("   ");
				}
			}
			System.out.println();
		}
	}
}